
public class JarlenLinkTest {

    public static void main(String[] args) {

        /*单链表反转*/
        Node linkNode = buildLink(5);
        System.out.print("创建单链表---> ");
        printLink(linkNode);
        Node reverseLinkNode = reverseLink(linkNode);
        System.out.print("反转单链表后---> ");
        printLink(reverseLinkNode);
        System.out.println();

        /*检测单链表中环的存在*/
        int linkLen = 9;
        int circlePosition = 4;
        Node circleLinkNode = buildCircleLink(linkLen, circlePosition);
        System.out.println("创建了一个长度为: " + linkLen + " 第一个环节点为 " + circlePosition + "的有环单链表");
        boolean existCircle = checkCycleInLink(circleLinkNode);
        System.out.println("当前链表是否有环: " + existCircle);
        System.out.println();

        /*删除链表倒数第 n 个结点*/
        Node deleteIndexNode = buildLink(5);
        System.out.print("删除链表倒数第 n 个结点--->单链表: ");
        printLink(deleteIndexNode);
        Node deleteResultNode = deleteLinkNode(deleteIndexNode, 1);
        System.out.print("删除后的单链表：");
        printLink(deleteResultNode);
        System.out.println();

        /*已知一个单链表中存在环，求进入环中的第一个节点*/
        int linkLen2 = 12;
        int circlePosition2 = 5;
        Node circleLinkNode2 = buildCircleLink(linkLen2, circlePosition2);
        Node firstNodeInCycle = getFirstNodeInCycle(circleLinkNode2);
        System.out.println("进入环中的第一个节点：" + firstNodeInCycle.data);
        System.out.println();

        /*检查一个单链表串是否是回文*/
        String palindromeString = "123454321";
        Node palindromeNode = buildPalindromeLink(palindromeString);
        System.out.print("回文单链表: ");
        printLink(palindromeNode);
        boolean isPalindromeLink = isPalindromeLink(palindromeNode);
        System.out.println(palindromeString + " 是否是回文---> " + isPalindromeLink);

    }

    /**
     * 求进入环中的第一个节点
     *
     * @param head
     * @return
     */
    private static Node getFirstNodeInCycle(Node head) {
        if (head == null) {
            return null;
        } else {
            Node fast = head;
            Node slow = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (fast == slow) {
                    slow = head;
                    while (slow != fast) {
                        slow = slow.next;
                        fast = fast.next;
                    }
                    return slow;
                }
            }
            return null;
        }
    }

    /**
     * 删除链表中第N个节点
     * 12345
     *
     * @param node 链表
     * @param endN 倒数第reciprocalN个
     * @return
     */
    private static Node deleteLinkNode(Node node, int endN) {

        Node pNode = node;
        int nodeCount = 0;
        while (pNode != null) {
            nodeCount++;
            pNode = pNode.next;
        }
        /*删除倒数第n的节点，也就是删除第 nodeCount-endN*/
        pNode = node;
        int n = nodeCount - endN;
        if (n == 0) {
            return pNode.next;
        }
        Node lastNode = node;
        int index = 0;
        while (pNode != null) {
            if (index == n) {
                lastNode.next = pNode.next;
                break;
            }
            lastNode = pNode;
            pNode = pNode.next;
            index++;
        }
        return node;
    }

    /**
     * 判断是否是回文链表
     * (递归)
     *
     * @param node
     * @return
     */
    private static boolean isPalindromeLink(Node node) {
        if (node.next == null) {
            return true;
        }

        Node firstNode = node;
        Node pSmallFirstNode = firstNode.next;

        Node pNode = node;
        Node pSmallEndNode = null;
        while (pNode.next != null) {
            pSmallEndNode = pNode;
            pNode = pNode.next;
        }
        if (!firstNode.data.equals(pSmallEndNode.next.data)) {
            return false;
        }
        pSmallEndNode.next = null;
        return isPalindromeLink(pSmallFirstNode);
    }

    /**
     * 將一個字符串轉換成單鏈表存儲的串
     *
     * @param palindromeStr 字符串
     * @return
     */
    private static Node buildPalindromeLink(String palindromeStr) {
        int len = palindromeStr.length();
        Node nextNode = new Node();
        nextNode.data = "" + palindromeStr.charAt(len - 1);
        nextNode.next = null;

        int index = len - 2;
        while (index >= 0) {
            Node node = new Node();
            node.data = "" + palindromeStr.charAt(index);
            node.next = nextNode;
            nextNode = node;
            index--;
        }
        return nextNode;
    }

    /**
     * 检查单链表中是否有环
     *
     * @param linkNode 单链表
     * @return
     */
    private static boolean checkCycleInLink(Node linkNode) {
        if (linkNode == linkNode.next) {
            return false;
        }
        if (linkNode == linkNode.next.next) {
            return true;
        }

        Node slow = linkNode;
        Node fast = linkNode.next.next;
        while (slow != null && fast != null) {
            if (slow == fast) {
                return true;
            }
            slow = slow.next;
            if (fast.next == null) {
                return false;
            }
            fast = fast.next.next;
        }
        return false;
    }

    /**
     * 构建一个有环的单链表
     *
     * @return
     */
    private static Node buildCircleLink(int linkLen, int circlePosition) {

        Node firstNode = null;
        Node firstCircleNode = null;
        Node pNode = null;
        for (int index = 1; index <= linkLen; index++) {
            Node node = new Node();
            if (pNode != null) {
                pNode.next = node;
            }
            node.data = "" + index;
            node.next = null;
            pNode = node;

            if (index == 1) {
                firstNode = node;
            }
            if (index == circlePosition) {
                firstCircleNode = node;
            }
        }
        pNode.next = firstCircleNode;
        return firstNode;
    }

    /**
     * 单链表反转
     *
     * @param linkNode
     * @return
     */
    private static Node reverseLink(Node linkNode) {
        if (linkNode.next == null) {
            return linkNode;
        }

        Node pNode = linkNode;
        Node newHeadNode = null;
        while (pNode != null) {
            Node node = pNode;
            pNode = pNode.next;

            node.next = newHeadNode;
            newHeadNode = node;
        }
        return newHeadNode;
    }

    /**
     * 构建一个单链表
     *
     * @return
     */
    private static Node buildLink(int linkLen) {
        Node nextNode = new Node();
        nextNode.data = "" + linkLen;
        nextNode.next = null;

        int index = linkLen - 1;
        while (index > 0) {
            Node node = new Node();
            node.data = "" + index;
            node.next = nextNode;
            nextNode = node;
            index--;
        }
        return nextNode;
    }

    /**
     * 打印链表
     *
     * @param node
     */
    private static void printLink(Node node) {
        Node pNode = node;
        while (pNode != null) {
            System.out.print("" + pNode.data);
            pNode = pNode.next;
        }
        System.out.println();
    }

    public static class Node {
        protected String data;
        protected Node next;
    }
}
